/*
 * @Author: your name
 * @Date: 2021-09-30 19:27:33
 * @LastEditTime: 2021-09-30 19:53:20
 * @LastEditors: Please set LastEditors
 * @Description: 简单实现二分查找，数组，找数
 * @FilePath: \luogu\1.6二分查找\模板\main.cpp
 */
#include<iostream>
#include<time.h>
using namespace std;

const int num = 5;

//返回结果下标，未找到返回-1
int binaryFind(int array[],int find_num);

int main(){
    int array[num];
    //简单顺序赋值
    for(int i=0; i<10; i++){
        array[i] = i;
    }
    //随机数初始
    srand(time(NULL));
    int find_num = rand()%num;
    cout << "find num : " << find_num << endl;
    cout << "index find : " << binaryFind(array,find_num);
    return 0;
}

int binaryFind(int array[],int find_num)
{
    int left = 0;
    int right = num-1;
    //这里mid向下取整,那么区间减半式必须保证左开右闭,否则会死循环
    int mid = (left+right)/2;
    //二分
    while(left <= right){
        //区间在左
        if(find_num <= array[mid]){
            right = mid; 
        }else{
            //左开
            left = mid + 1;
        }
        mid = (left + right)/2;
    }

    /*
        这里给出mid向上取整,区间减半保证左闭右开
        int mid = (left+right)/2;
        while(left < right){
            //区间在左
            if(find_num < array[mid]){
                //右开
                right = mid-1;
            }else{
                left = mid;
            }
        }
    */
    //确定是否找到
    if(left == right){
        return left;
    }
    //失败
    return -1;
}